문제
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행
[a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예
| n | vertex | return |
|---|---|---|
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] |
3 |
입출력 예 설명
예제의 그래프를 최단 경로 계층별로 시각화하면 다음과 같습니다.
- 1번 노드와의 거리 1: 2번, 3번 노드
- 1번 노드와의 거리 2: 4번, 5번, 6번 노드
1번 노드에서 가장 멀리 떨어진 노드는 4, 5, 6번 노드이므로, 총 3을 반환합니다.
문제 풀이
가장 먼 노드를 찾는 문제는 자료 구조 시간에 배우는 가장 정석적인 알고리즘이지만 여기서는 가장 먼 노드들을 찾는 문제이다. 하나의 노드만을 찾는 것이 아니고 여럿을 찾아야 한다. 이 때 BFS를 단순히 여러 번을 돌리면 BFS 탐색에 걸리는 시간 * 반복 횟수이기 때문에 문제의 노드 수를 봐서 시간 초과이다. 이런 경우 영리한 전략을 세워야 한다.
BFS에서 깊이는 기준점으로부터의 거리이다. 그 말은 문제에서 말한 1번 노드로부터 탐색하며 각 노드의 깊이를 기록해 가장 깊은 노드와 같은 깊이를 가진 노드를 찾으면 된다. 사진학에서의 비유를 이용하자면 이것은 깊이보다 심도라고 칭하는 것이 더 정확하다. 말하자면, 현재 포커싱 존이 충분히 좁고 존으로부터 3m 떨어진 피사체가 있다고 하면 존으로부터 3미터 반경 내외의 피사체에 대한 심도는 동일한 것이다.
그렇다면 일단 다음 노드가 무엇인지 간선 정보를 저장하는 vector<int> * 형으로 연속된 메모리 공간을 잡아 준다.
가장 편하게 배열을 이용해서 메모리 공간을 잡아 주자.
vector<int> nodes[20001];
과 같이 선언하면 스택 영역에 20001개의 연속된 정수 벡터가 생긴다. STL 타입들은 동적 할당 시에 C++ 스타일이고 C스타일을 선호하는 작업자에게는 호불호가 갈린다. 이런 코딩 테스트에서는 자원을 많이 소모하지 않는다면 배열로 두는 것도 나쁘지 않다.
다음으로 필요한 것들은 *depth와 *visited이다. 1-based Index를 이용해 주기 위해서 입력받은 크기 N에 1을 더해서 N+1만큼 힙 영역에 동적 할당한다.
메모리를 0으로 채우는 시간을 아끼기 위해 Zero-Fill을 위한 최적화가 잘 된 C의 calloc을 빌리도록 하자.
BFS 코드에서 반드시 심도를 세어 줘야 한다. BFS 부분만을 떼서 작성하자면 아래와 같다.
int bfs() { // return deepest depth from 1th node
queue<int> q;
q.push(1);
depth[1] = 1;
int max_depth = 1 ;
int current_node = 1 ;
visited[1] = true;
while(!q.empty()) {
if(!q.empty()) {
current_node = q.front();
q.pop();
} else {
break; // duplicate safe code; can be removed when developing production code?
}
visited[current_node] = true;
for(int i = 0; i < nodes[current_node].size(); i++) {
int next = nodes[current_node][i];
if(!visited[next]) {
visited[next] = true ;
q.push (next) ;
depth [next] =
depth[current_node] + 1; // 매우 중요한 부분. 심도를 센다.
max_depth = max(max_depth,
depth[next]); // 심도만 센다고 되는 것이 아니다. 심도를 센 후 가장 깊은 심도라면 기록한다.
}
}
}
return max_depth;
}
이를 이용하면 가장 깊은 심도를 잴 수가 있다.
int depth_target = bfs();
for(int i = 1; i <= n; i++) {
if(depth[i] == depth_target) answer++;
}
이를 이용하여 같은 심도를 가진 노드의 수를 세어 주면 정답이다.
잡다한 노동에서 알아둘 점
프로그래머스가 solution 함수만을 받는 이유는 함수가 자신들의 main 안에서 호출되고 변수들은 코드 맥락에서 재활용되게 하는 것을 유도하는 데에 있다.
할당한 변수, 배열, 메모리 공간 등은 그때그때 비우거나 Zero-Fill한다. 그러나 C++ STL 등의 복잡한 자료들을 Zero-Fill로 처리한다고 생각하지 말자.
또한, 이러한 코딩 테스트는 시간 복잡도를 중요하게 보지만, N이 십만이 넘더라도 단일 반복문까지 불가능한 문제는 굉장히 고난도 문제이다.
웬만한 경우에는 log(N)만큼의 시간복잡도 추가에 관용적이다. 필요에 따라 다익스트라, A* 등의 높은 시간 복잡도를 가진 알고리즘을 사용해야 한다면 가능한 한 적은 횟수로 명시적 호출하도록 하자.
완성된 풀이
#include <string>
#include <vector>
#include <cstdlib> // to use calloc
#include <cstring> // to use memset
#include <queue>
using namespace std;
vector<int> nodes[20001];
int *depth ;
bool *visited;
int bfs() { // return deepest depth from 1th node
queue<int> q;
q.push(1);
depth[1] = 1;
int max_depth = 1 ;
int current_node = 1 ;
visited[1] = true;
while(!q.empty()) {
if(!q.empty()) {
current_node = q.front();
q.pop();
} else {
break; // duplicate safe code; can be removed when developing production code?
}
visited[current_node] = true;
for(int i = 0; i < nodes[current_node].size(); i++) {
int next = nodes[current_node][i];
if(!visited[next]) {
visited[next] = true ;
q.push (next) ;
depth [next] =
depth[current_node] + 1;
max_depth = max(max_depth,
depth[next]);
}
}
}
return max_depth;
}
int solution(int n, vector<vector<int>> edge) {
int answer = 0;
for(int i = 0; i < 20001; i++) {
nodes[i].clear();
}
depth = (int *) calloc((size_t) n+1, sizeof(int ));
for(int i = 0; i <= n; i++) nodes[i].clear();
visited = (bool*) calloc((size_t) n+1, sizeof(bool ));
for(auto e: edge) {
nodes[e[0]].push_back(e[1]);
nodes[e[1]].push_back(e[0]);
}
int depth_target = bfs();
for(int i = 1; i <= n; i++) {
if(depth[i] == depth_target) answer++;
}
free(depth);
free(visited);
return answer;
}